package com.graph;

import java.util.LinkedList;

public class Solution934 {
    LinkedList<int[]> queue = new LinkedList<>();
    public int shortestBridge(int[][] grid) {
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        int[] dx = new int[]{-1, 1, 0, 0};
        int[] dy = new int[]{0, 0, -1, 1};
        boolean flag = false;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    dfs(grid, visited, i, j);
                    flag = true;
                    break;
                }
            }
            if (flag) break;
        }
        int[] cur = null;
        int res = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                cur = queue.removeFirst();
                for (int j = 0; j < 4; j++) {
                    int x = cur[0] + dx[j];
                    int y = cur[1] + dy[j];
                    if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || visited[x][y]) continue;
                    if (grid[x][y] == 1) return res;
                    visited[x][y] = true;
                    queue.add(new int[]{x, y});
                }
            }
            res++;
        }
        return res;
    }

    public void dfs(int[][] grid, boolean[][] visited, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return;
        if (visited[i][j] || grid[i][j] == 0) return;
        visited[i][j] = true;
        queue.add(new int[]{i, j});
        dfs(grid, visited, i - 1, j);
        dfs(grid, visited, i + 1, j);
        dfs(grid, visited, i, j - 1);
        dfs(grid, visited, i, j + 1);
    }
}
